#define _CRT_SECURE_NO_WARNINGS 1

#include "Queue.h"

void QueueInit(Queue* pQ) 
{
    assert(pQ);

    pQ->pHead = pQ->pTail = NULL;
}

void QueueDestroy(Queue* pQ) 
{
    assert(pQ); 

    QueueNode* cur = pQ->pHead;
    while (cur != NULL) 
    {
        QueueNode* curNext = cur->next;  //防止释放cur后找不到其下一个节点
        free(cur);                     
        cur = curNext;                   
    }
    pQ->pHead = pQ->pTail = NULL; 
}

bool QueueEmpty(Queue* pQ) 
{
    assert(pQ); 

    return pQ->pHead == NULL;//如果成立则为True，不成立则为False
}

//入队：队尾入数据，队头出(删)数据。如果是第一个入队的(队列为空)则既要当头又当尾
void QueuePush(Queue* pQ, QueueDataType x) 
{
    assert(pQ);

    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    if (new_node == NULL)
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    new_node->data = x;     //待插入的数据
    new_node->next = NULL;  //新的数据指向空

    if (pQ->pHead == NULL)//情况1: 队列为空
    {           
        pQ->pHead = pQ->pTail = new_node;
    }
    else //情况2: 队列不为空   队尾入数据
    {                              
        pQ->pTail->next = new_node;  //在现有尾的后一个节点放置new_node
        pQ->pTail = new_node;        //更新pTail，使它指向新的尾
    }
}

void QueuePop(Queue* pQ) // 出队：队尾入数据，队头出(删)数据
{
    assert(pQ);                          
    assert(!QueueEmpty(pQ));  

    QueueNode* headNext = pQ->pHead->next; //队头出数据，防止释放pHead后找不到其下一个节点
    free(pQ->pHead);
    pQ->pHead = headNext;                  //更新头 

    if (pQ->pHead == NULL)//删完之后 pHead == NULL 了 pTail 还是野指针
    {
        pQ->pTail = NULL;//处理一下尾指针，将尾指针置空
    }
}

QueueDataType QueueFront(Queue* pQ) //返回队头数据
{
    assert(pQ);                           
    assert(!QueueEmpty(pQ));    

    return pQ->pHead->data;
}

QueueDataType QueueBack(Queue* pQ) //返回队尾数据
{
    assert(pQ);
    assert(!QueueEmpty(pQ));

    return pQ->pTail->data;
}

int QueueSize(Queue* pQ) //返回队列大小
{
    assert(pQ);

    int count = 0;
    QueueNode* cur = pQ->pHead;
    while (cur != NULL) 
    {
        count++;
        cur = cur->next;
    }
    return count;
}
//
////力扣链接：225.用队列实现栈
////难度简单
////请你仅使用两个队列实现一个后入先出（LIFO）的栈，
////并支持普通栈的全部四种操作（push、top、pop 和 empty）。
////实现 MyStack 类：
////? void push(int x) 将元素 x 压入栈顶。
////? int pop() 移除并返回栈顶元素。
////? int top() 返回栈顶元素。
////? boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
//typedef struct {
//    Queue q1;
//    Queue q2;
//} MyStack;
//
//
//MyStack* myStackCreate() {
//    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
//    QueueInit(&st->q1);//q1是结构体，还要取地址
//    QueueInit(&st->q2);//q2是结构体，还要取地址
//    return st;
//}
//
//void myStackPush(MyStack* obj, int x) {
//    if (!QueueEmpty(&obj->q1))//q1不为空（入到q1）
//    {
//        QueuePush(&obj->q1, x);
//    }
//    else//q2不为空（入到q2），或者两个都为空（入到哪都行）
//    {
//        QueuePush(&obj->q2, x);
//    }
//}
//
//int myStackPop(MyStack* obj) {
//    //题目要求int pop() 移除并返回栈顶元素。
//    //法一：
//    //if (!QueueEmpty(&obj->q1))//q1不为空,转移到q2保存，只剩最后一个时Pop掉
//    //{
//    //    while (QueueSize(&obj->q1) > 1)
//    //    {
//    //        QueuePush(&obj->q2, QueueFront(&obj->q1));//从q1取数据Push到q2
//    //        QueuePop(&obj->q1);
//    //    }
//    //    int ret = QueueFront(&obj->q1);
//    //    QueuePop(&obj->q1);//题目要求int pop() 移除并返回栈顶元素。
//    //    return ret;
//    //}
//    //else//q2不为空,转移到q1保存，只剩最后一个时Pop掉
//    //{
//    //    while (QueueSize(&obj->q2) > 1)
//    //    {
//    //        QueuePush(&obj->q1, QueueFront(&obj->q2));//从q2取数据Push到q1
//    //        QueuePop(&obj->q2);
//    //    }
//    //    int ret = QueueFront(&obj->q2);
//    //    QueuePop(&obj->q2);
//    //    return ret;
//    //}
//    //法二：
//    Queue* emptyQ = &obj->q1;//假设q1为空 q2非空
//    Queue* nonemptyQ = &obj->q2;
//    if (!QueueEmpty(&obj->q1))//假设失败，倒过来
//    {
//        emptyQ = &obj->q2;
//        nonemptyQ = &obj->q1;
//    }
//    while (QueueSize(nonemptyQ) > 1)
//    {
//        QueuePush(emptyQ, QueueFront(nonemptyQ));//从非空队列取数据Push到空队列
//        QueuePop(nonemptyQ);
//    }
//    int ret = QueueFront(nonemptyQ);
//    QueuePop(nonemptyQ);
//    return ret;
//}
//
//int myStackTop(MyStack* obj) {
//    //题目要求int top() 返回栈顶元素。（队列尾）队列不能删尾，能取尾
//    if (!QueueEmpty(&obj->q1))//q1不为空
//    {
//        return QueueBack(&obj->q1);
//    }
//    else//q2不为空
//    {
//        return QueueBack(&obj->q2);
//    }
//}
//
//bool myStackEmpty(MyStack* obj) {
//    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
//}
//
//void myStackFree(MyStack* obj) {
//    QueueDestroy(&obj->q1);
//    QueueDestroy(&obj->q2);
//    free(obj);
//}
//
////力扣链接：622.设计循环队列
////难度中等
////设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则
////并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
////循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，
////一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，
////我们能使用这些空间去存储新的值。
////你的实现应该支持如下操作：
////? MyCircularQueue(k) : 构造器，设置队列长度为 k 。
////? Front : 从队首获取元素。如果队列为空，返回 - 1 。
////? Rear : 获取队尾元素。如果队列为空，返回 - 1 。
////? enQueue(value) : 向循环队列插入一个元素。如果成功插入则返回真。
////? deQueue() : 从循环队列中删除一个元素。如果成功删除则返回真。
////? isEmpty() : 检查循环队列是否为空。
////? isFull() : 检查循环队列是否已满。
//
//typedef struct {
//    //匿名结构体
//    int* arr;
//    int front;
//    int tail;
//    int k;
//} MyCircularQueue;
//bool myCircularQueueIsEmpty(MyCircularQueue* obj);
//bool myCircularQueueIsFull(MyCircularQueue* obj);
//
//MyCircularQueue* myCircularQueueCreate(int k) {
//    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//    //OJ题一般都会开辟空间成功，不用判空了
//    cq->arr = (int*)malloc(sizeof(int) * (k + 1));//初始化 开k+1个空间
//    cq->front = cq->tail = 0;
//    cq->k = k;
//    return cq;
//}
//
//bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//    //enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
//    //(失败返回假)满了就失败  
//    //先滑到下面实现myCircularQueueIsFull和myCircularQueueIsEmpty，记得在上面声明
//    if (myCircularQueueIsFull(obj))
//    {
//        return false;
//    }
//    obj->arr[obj->tail] = value;
//    obj->tail++;
//    obj->tail %= (obj->k + 1);//超出k+1就模到0从头开始，没超，模和没模一样
//    return true;
//}
//
//bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//    //deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
//    if (myCircularQueueIsEmpty(obj))
//    {
//        return false;
//    }
//    obj->front++;  //不理解可以看上面的图
//    obj->front %= (obj->k + 1); //超出k+1就模到0从头开始，没超，模和没模一样
//    return true;
//}
//
//int myCircularQueueFront(MyCircularQueue* obj) {
//    //Front: 从队首获取元素。如果队列为空，返回 -1 。
//    if (myCircularQueueIsEmpty(obj))
//    {
//        return -1;
//    }
//    return obj->arr[obj->front];
//}
//
//int myCircularQueueRear(MyCircularQueue* obj) {
//    //Rear: 获取队尾元素。如果队列为空，返回 -1 。
//    if (myCircularQueueIsEmpty(obj))
//    {
//        return -1;
//    }
//    if (obj->tail == 0)//如果tail在0上，返回tail的上一个就是k
//    {
//        return obj->arr[obj->k];
//    }
//    else
//    {
//        return obj->arr[obj->tail - 1];
//    }
//}
//
//bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
//    return obj->front == obj->tail; //看上面判空和判满条件
//}
//
//bool myCircularQueueIsFull(MyCircularQueue* obj) {
//    return (obj->tail + 1) % (obj->k + 1) == obj->front;
//}
//
//void myCircularQueueFree(MyCircularQueue* obj) {
//    free(obj->arr);
//    free(obj);      //有两层  结构体里面有个数组
//}
//
///**
// * Your MyCircularQueue struct will be instantiated and called as such:
// * MyCircularQueue* obj = myCircularQueueCreate(k);
// * bool param_1 = myCircularQueueEnQueue(obj, value);
//
// * bool param_2 = myCircularQueueDeQueue(obj);
//
// * int param_3 = myCircularQueueFront(obj);
//
// * int param_4 = myCircularQueueRear(obj);
//
// * bool param_5 = myCircularQueueIsEmpty(obj);
//
// * bool param_6 = myCircularQueueIsFull(obj);
//
// * myCircularQueueFree(obj);
//*/